extern "C"
__global__ void fft(int size, int N, float* a, float* wi_list, float* wj_list){
	int step;
	int step2;
	int countThreads = 16;
	int flag = 0;
	//int ID = ceil(threadIdx.x/4);
 	
	//int downMatrIndex;
	//int downMirrIndex;
	//int rightMatrIndex;
	//int rightMirrIndex;
	int dsInd;
	int raInd;
	int rbInd;
	int rcInd;
	int rdInd;
	int rsaInd;
	int rsbInd;
	int rscInd;
	int rsdInd;
	int wiInd;
	int wjInd;
	float w1[4];
	float w2[4];
	float tmp[4];
	float tmp2[4];
	
	float a00a;
	float a00b;
	float a00c;
	float a00d;
	float a01a;
	float a01b;
	float a01c;
	float a01d;
	float a10a;
	float a10b;
	float a10c;
	float a10d;
	float a11a;
	float a11b;
	float a11c;
	float a11d;
	
	int a00ai;
	int a00bi;
	int a00ci;
	int a00di;
	int a01ai;
	int a01bi;
	int a01ci;
	int a01di;
	int a10ai;
	int a10bi;
	int a10ci;
	int a10di;
	int a11ai;
	int a11bi;
	int a11ci;
	int a11di;
	
	for (int q = 0; q < size; q++) {
		step = ceil(pow(2.0f,q));
		step2 = step*2;
		for (int down = threadIdx.y; down < N - step; down = down + countThreads) {
			for (int right = threadIdx.x; right < N - step; right = right + countThreads) {
				flag = (down/step) % 2;
				flag = flag + (right/step) % 2;
				if (flag == 0){
					wiInd = (down % step2)*(N/step2) * 4;
					wjInd = (right % step2)*(N/step2) * 4;
					w1[0] = wi_list[wiInd];
					w1[1] = wi_list[wiInd+1];
					w1[2] = wi_list[wiInd+2];
					w1[3] = wi_list[wiInd+3];
					w2[0] = wj_list[wjInd];
					w2[1] = wj_list[wjInd+1];
					w2[2] = wj_list[wjInd+2];
					w2[3] = wj_list[wjInd+3];
					
					dsInd = down + step;
					raInd = 4*right;
					rbInd = raInd + 1;
					rcInd = raInd + 2;
					rdInd = raInd + 3;
					rsaInd = 4*(right+step);
					rsbInd = rsaInd+1;
					rscInd = rsaInd+2;
					rsdInd = rsaInd+3;
					
					a00ai = down*N*4 + raInd;
					a00bi = a00ai + 1;
					a00ci = a00ai + 2;
					a00di = a00ai + 3;
					
					a01ai = down*N*4 + rsaInd;
					a01bi = a01ai + 1;
					a01ci = a01ai + 2;
					a01di = a01ai + 3;
					
					a10ai = dsInd*N*4 + raInd;
					a10bi = a10ai + 1;
					a10ci = a10ai + 2;
					a10di = a10ai + 3;
					
					a11ai = dsInd*N*4 + rsaInd;
					a11bi = a11ai + 1;
					a11ci = a11ai + 2;
					a11di = a11ai + 3;
					
					
					//XXX = XXX.add(a00);
					a00a = a[a00ai];
					a00b = a[a00bi];
					a00c = a[a00ci];
					a00d = a[a00di];
					
					a10a = a[a00ai];
					a10b = a[a00bi];
					a10c = a[a00ci];
					a10d = a[a00di];
					
					a01a = a[a00ai];
					a01b = a[a00bi];
					a01c = a[a00ci];
					a01d = a[a00di];
					
					a11a = a[a00ai];
					a11b = a[a00bi];
					a11c = a[a00ci];
					a11d = a[a00di];
					
					
					//XXX = XXX.add(t1.multy(a10));
					tmp[0] = w1[0]*a[a10ai] - w1[1]*a[a10bi] - w1[2]*a[a10ci] + w1[3]*a[a10di];
					a00a = a00a + tmp[0];
					a10a = a10a - tmp[0];
					a01a = a01a + tmp[0];
					a11a = a11a - tmp[0];
					
					tmp[1] = w1[0]*a[a10bi] + w1[1]*a[a10ai] - w1[2]*a[a10di] + w1[3]*a[a10ci];
					a00b = a00b + tmp[1];
					a10b = a10b - tmp[1];
					a01b = a01b + tmp[1];
					a11b = a11b - tmp[1];
					
					tmp[2] = w1[0]*a[a10ci] - w1[1]*a[a10di] + w1[2]*a[a10ai] - w1[3]*a[a10bi];
					a00c = a00c + tmp[2];
					a10c = a10c - tmp[2];
					a01c = a01c + tmp[2];
					a11c = a11c - tmp[2];
					
					tmp[3] = w1[0]*a[a10di] + w1[1]*a[a10ci] + w1[2]*a[a10bi] + w1[3]*a[a10ai];							
					a00d = a00d + tmp[3];
					a10d = a10d - tmp[3];
					a01d = a01d + tmp[3];
					a11d = a11d - tmp[3];
					
					
					//XXX = XXX.add(t2.multy(a01));
					tmp[0] = w2[0]*a[a01ai] - w2[1]*a[a01bi] - w2[2]*a[a01ci] + w2[3]*a[a01di];
					a00a = a00a + tmp[0];
					a10a = a10a + tmp[0];
					a01a = a01a - tmp[0];
					a11a = a11a - tmp[0];
					
					tmp[1] = w2[0]*a[a01bi] + w2[1]*a[a01ai] - w2[2]*a[a01di] + w2[3]*a[a01ci];
					a00b = a00b + tmp[1];
					a10b = a10b + tmp[1];
					a01b = a01b - tmp[1];
					a11b = a11b - tmp[1];
					
					tmp[2] = w2[0]*a[a01ci] - w2[1]*a[a01di] + w2[2]*a[a01ai] - w2[3]*a[a01bi];
					a00c = a00c + tmp[2];
					a10c = a10c + tmp[2];
					a01c = a01c - tmp[2];
					a11c = a11c - tmp[2];
					
					tmp[3] = w2[0]*a[a01di] + w2[1]*a[a01ci] + w2[2]*a[a01bi] + w2[3]*a[a01ai];	
					a00d = a00d + tmp[3];
					a10d = a10d + tmp[3];
					a01d = a01d - tmp[3];
					a11d = a11d - tmp[3];
					
					//XXX = XXX.add(t1.multy(t2.multy(a11)));
					tmp[0] = w2[0]*a[a11ai] - w2[1]*a[a11bi] - w2[2]*a[a11ci] + w2[3]*a[a11di];
					tmp[1] = w2[0]*a[a11bi] + w2[1]*a[a11ai] - w2[2]*a[a11di] + w2[3]*a[a11ci];
					tmp[2] = w2[0]*a[a11ci] - w2[1]*a[a11di] + w2[2]*a[a11ai] - w2[3]*a[a11bi];
					tmp[3] = w2[0]*a[a11di] + w2[1]*a[a11ci] + w2[2]*a[a11bi] + w2[3]*a[a11ai];	
					tmp2[0] = w1[0]*tmp[0] - w1[1]*tmp[1] - w1[2]*tmp[2] + w1[3]*tmp[3];
					tmp2[1] = w1[0]*tmp[1] + w1[1]*tmp[0] - w1[2]*tmp[3] + w1[3]*tmp[2];
					tmp2[2] = w1[0]*tmp[2] - w1[1]*tmp[3] + w1[2]*tmp[0] - w1[3]*tmp[1];
					tmp2[3] = w1[0]*tmp[3] + w1[1]*tmp[2] + w1[2]*tmp[1] + w1[3]*tmp[0];	
					
					a00a = a00a + tmp2[0];
					a00b = a00b + tmp2[1];
					a00c = a00c + tmp2[2];
					a00d = a00d + tmp2[3];
					
					a10a = a10a - tmp2[0];
					a10b = a10b - tmp2[1];
					a10c = a10c - tmp2[2];
					a10d = a10d - tmp2[3];
					
					a01a = a01a - tmp2[0];
					a01b = a01b - tmp2[1];
					a01c = a01c - tmp2[2];
					a01d = a01d - tmp2[3];
					
					a11a = a11a + tmp2[0];
					a11b = a11b + tmp2[1];
					a11c = a11c + tmp2[2];
					a11d = a11d + tmp2[3];
					
				
					
					a[a00ai] = a00a;
					a[a01ai] = a01a;
					a[a10ai] = a10a;
					a[a11ai] = a11a;
					
					a[a00bi] = a00b;
					a[a01bi] = a01b;
					a[a10bi] = a10b;
					a[a11bi] = a11b;
					
					a[a00ci] = a00c;
					a[a01ci] = a01c;
					a[a10ci] = a10c;
					a[a11ci] = a11c;
					
					a[a00di] = a00d;
					a[a01di] = a01d;
					a[a10di] = a10d;
					a[a11di] = a11d;
					
				}	
			}
		}
		__syncthreads();
	}
}